Educational Codeforces Round83 A~E题解

A

打的时候猜了一个结论:n % m == 0时才能画出来,具体详细一点的证明可能不太会写,如果以后理解了就回来补一下,这里也不提这个题了毕竟只是A
代码:https://codeforces.com/contest/1312/submission/72794306

B

大意:
如果整个序列中所有元素都满足: i < j && j - a[j] != i - a[i],则称这个序列时好序列。现给你一个序列a,只允许你打乱整个序列,输出一种可能的方案使得这个序列是好序列。
分析:
注意题目中所说的一个条件:It's guaranteed that it's always possible to shuffle an array to meet this condition.也就是说一定是有解的,这个时候就可以猜一下结论了,很有可能是直接排序后输出就可以了。然后根据条件有i < j时满足j - a[j] != i - a[i],这实际上是说j - i != a[j] - a[i],而下标是定的,i一定在j前面,也就是说j总是大于i的,那么j-i也一定是大于0的,如果要让一个序列满足条件,是不是让整个序列倒序过来,就一定会让后面的数不大于前面的数,即a[j] <= a[i] => a[j] - a[i] <= 0,在一定有解的条件下,我们到这里就可以验证知道倒序就一定是正确的答案了。
代码:https://codeforces.com/contest/1312/submission/72808043

C

大意:
给你一个初始全0的序列,每一步你可以选择这样两个操作:①跳过这一轮②给某一个位置上的数增加k^i,其中i是当前的步数(步数从0开始),问是否可以通过如上的两种操作,使得整个序列最终和所给的序列相等。(只需要输出正确与否)
分析:
这个题就是验证数组中的每一个数是不是都可以按题目中所给的操作得到。观察后可以发现题目中所说的给一个位置上的数加上ki换成"是否可以由多个不同的i对应的ki加和得到"与一个"任意一个数可以分解成2^i0 + 2^i1 + 2i2......+2in"这个分解有很相像之处,进一步的,我们其实可以把这个2进制的分解定理拓展成k进制的分解 ,即任意数p = An1 * k^i1 + An2 * k ^i2 + An3 * k i3.....+Ann*kin(Ai表示在k进制下的p某一位数,其中任意的Ai都满足取值范围∈[0,k-1])。其次,由于每次加和的数都只能是k^i,因此对于一个可以拼凑的数来说,分解之后每一位数都必须是0或者1,否则就凑不出来;同时每一步只能给一个位置的数加一次和,因此如果某一位数是1,那么同时也要满足序列中其他的数也必须要满足这一位不能是1,也就是说在k进制下所有数这一位要么全部是0要么只有一个是1,其他的都错。至此可以总结出这个题的两个关键结论:①所有数在k进制下,每一位要么是0要么是1②如果有一位是1,那么必须满足其他所有数这一位不能是1。
代码:https://codeforces.com/contest/1312/submission/72887517

D

大意:
输入两数n和m,问有多少种满足以下条件的序列
①长度为n
②整个序列满足有一个分界点,前面是严格上升序列,后面是严格下降序列
③序列中有且仅有一对重复的数
④序列中的数范围是1~m
分析:
这是一道很典型的组合计数问题,我们从以下两个方向入手:
①确定序列:首先这个题元素范围是限定在了1~m之间的,其次有且仅有一对重复元素,因此是m个数中选择了n-2个数(有一对重复了,还要选一个最大值出来)再从其中选取一个数作为重复的数,即C(m,n - 2)x(n - 2);其次思考整个序列中有没有已经确定了的元素,我们可以发现一个性质:对于最大的数来说,他一定是作为分界点的,并且两个重复的数字一定在他的两边,这是因为数列中要有一对重复的数并且满足严格上升和严格下降,如果在一边就一定不满足:到这里我们可以确定这个序列一定是长成"某个相同的数___最大值___某个相同的数"这个样子的。这一步方案数总体是C(m,n-2) * (n - 2)
②选数完善:在上一步中我们已经确定了整个序列长什么样,这一步要完成的是整个序列剩余的空缺怎么选择的问题:对于已经选了的数之外的n-3个数,每一种数都有2种排法,即在分界点的左边或者右边(在重复的数左边或者右边是不影响的,跟方案数无关,因为一个数在左边或者在右边与那个重复的数之间的位置关系一定是已经确定了的)也就是说这一步方案数总体是2^(n-3)
不过需要特别注意的是,对于n=2的情况是无解的,需要特判否则会在第六个点TLE。
最后两个步骤按乘法原理相乘即可,具体实现中由于数字很大并且涉及取模,需要使用乘法逆元,如果不了解乘法逆元可以先了解一下。
代码:https://codeforces.com/contest/1312/submission/72887256

E

大意:
给你一个长度为n的序列,每次你可以选择两个相邻且相同的数,把他们删去,并用数值+1插入原来的位置。你需要计算出整个序列在经历若干次操作后,最短的长度是多少。
分析:
对于一对数合并的操作,如果把一对数拓展到两个相邻的区间合并,就启发我们这个题可以用区间dp来做,用一个O(N^3),N<=500给2s这个时间复杂度上没有问题,接着往下想,如果按正向思考会发现一个问题:合并这个操作会带来下标的变化,这样变化之后似乎很难正向突破,要处理的东西变得很复杂。但是对一个区间来说,中间的过程是怎样的我们并不关心,我们只关注一个区间最终可以合并成多少,这里就有一个结论:对于区间[l,r]来说最终可以合并成一个唯一的数(不存在多解)。
定义状态f[l,r]是整个区间f[l,r]最终可以合并得到的数,如果不能合并则是0。
对于这个状态来说
①初态:f[i][i] = a[i],其余为0。
②状态转移:在可以合并的条件下:f[l][r] = max{f[l,k] + f[k+1][r] + 1},其余为0;
③终态:我们发现结果好像不怎么好求,因为题目问的不是最终的数是谁而是区间长度,这里我们再引入一个状态:steps[l][r]表示区间[l,r]通过合并最多可以去掉多少个数,来完成这个问题的求解。
对于steps[l][r]来说
①初态:所有值都是0
②状态转移:在可以合并的条件下steps[l][r] = max{steps[l][k] + steps[k+1][r] + 1},其余为steps[l][r] = max{steps[l][k] + steps[k+1][r]};
③终态:max{steps[l][r]},这个在递推的过程中就可以直接得到了(但是要注意一点是这里求的是最多能够去掉多少个数,因此最终的答案要写成n-最多能去掉的数)。
到此我们就把整个E题做出来了,使用两个递推,整体复杂度是O(N^3 + N^2) = O(N^3)的。
代码:https://codeforces.com/contest/1312/submission/72898836